The present application relates to information encoding for transmission over noisy channels and storage, and more particularly to error resilient encoding.
Two common approaches to the mitigation of errors arising during the transmission of data over noisy channels exist: Automatic Retransmission Request (ARQ) and Forward Error Correction (FEC). ARQ type of mitigation typically would not be feasible in multicast or real-time applications such as video because of intolerable time delays or a lack of feedback channel. In such cases, a decoder can only decode the error corrupted bitstream, protected to an extent by error correction encoding, and must create from such bitstream. FEC provides mitigation by error correcting codes (e.g., Reed-Solomon). However, uncorrectable errors require further mitigated approaches.
In general, commonly used video compression methods have block-based motion compensation to remove temporal redundancy. Motion compensation methods encode only (macro) block motion vectors and the corresponding quantized residuals (texture); and variable length coding (VLC) of the motion vectors and residual increases coding efficiency. However, variable length coding often are highly susceptible to transmission channel errors and a decoder easily loses synchronization with the encoder when uncorrectable errors arise. The predictive coding methods, such as motion compensation, make matters much worse because the errors in one video frame quickly propagate across the entire video sequence and rapidly degrade the decoded video quality.
The typical approach of such block-based video compression methods to uncorrectable errors includes the steps of error detection (e.g., out-of-range motion vectors, invalid VLC table entry, or invalid number of residuals in a block), resynchronization of the decoder with the encoder, and error concealment by repetition of previously transmitted correct data in place of the uncorrectable data. For example, video compressed using MPEG1-2 has a resynchronization marker (start code) at the start of each slice of macroblocks (MBs) of a frame, and an uncorrectable error results in all of the data between correctly decoded resynchronization markers being discarded. This implies degradation in quality of the video stream, especially for predictive compression methods such as MPEG.
This compressed video is typically coded using Variable Length Code (VLC) tables such as Huffman codes. When the compressed video data is transmitted over noisy communication channels, it is corrupted by channel errors. VLC tables prove to be particularly sensitive to bit errors. This is because bit errors can make one codeword be incorrectly interpreted to be another codeword of a different length and hence the error is not detected. This makes the decoder lose synchronization with the encoder. Although the error may finally be detected due to an invalid VLC table entry, usually the location in the bitstream where the error is detected is not the same as the location where the error occurred. Hence, when the decoder detects an error, it has to seek the next resynchronization marker and discard all the data between this and the previous resynchronization marker. Thus, even a single bit error can sometimes result in a loss of a significant amount of data, and this is a problem of the known coding schemes.
Golomb-Rice codes (S. W. Golomb, xe2x80x9cRun-length encodings,xe2x80x9d IEEE Trans. Inf. Theory, vol. IT-12, pp. 399-401, July 1966 and R. F. Rice, xe2x80x9csome practical universal noiseless coding techniques,xe2x80x9d Tech. Rep. JPL-79-22, Jet Propulsion Laboratory, Pasadena, Calif., March 1979) have been applied to lossless image compression; see M. J. Weinberger, G. Seroussi, and G. Sapiro, xe2x80x9cLOCO-l: A low complexity, context based lossless image compression algorithm,xe2x80x9d Por.c 1996 IEEE Data Comp. Conf., Snowbird, Utah, pp.140-149, April, 1996.
These video compression and decompression methods may be implemented on special integrated circuits or on programmable digital signal processors or microprocessors.
The present invention uses reversible VLC (RVLC) tables based on Golomb-Rice codes to alleviate the error problems in motion compensated compressed video such as MPEG. These RVLC tables have the property that they can be uniquely decoded both in the forward and the backward (reverse) directions. This property enables a decoder to better isolate the location of the error and minimize the amount of data that needs to be discarded.
Preferred embodiments present different kinds RVLCs for each of (1) motion header data (COD+MCBPC) (for INTRA and INTER frames), (2) motion vector data, (3) INTRA DCT coefficient data. and (4) INTER DCT coefficient data.
This has the advantage of better performance with efficient codes.